package main

import (
	"fmt"
	"strings"
)

/*
Students may decide to take different "tracks" or sequences of courses in the Computer Science curriculum. There may be more than one track that includes the same course, but each student follows a single linear track from a "root" node to a "leaf" node. In the graph below, their path always moves left to right.

Write a function that takes a list of (source, destination) pairs, and returns the name of all of the courses that the students could be taking when they are halfway through their track of courses.

Sample input:
all_courses = [
    ["Logic", "COBOL"],
    ["Data Structures", "Algorithms"],
    ["Creative Writing", "Data Structures"],
    ["Algorithms", "COBOL"],
    ["Intro to Computer Science", "Data Structures"],
    ["Logic", "Compilers"],
    ["Data Structures", "Logic"],
    ["Creative Writing", "System Administration"],
    ["Databases", "System Administration"],
    ["Creative Writing", "Databases"],
    ["Intro to Computer Science", "Graphics"],
]

Sample output (in any order):
          ["Data Structures", "Creative Writing", "Databases", "Intro to Computer Science"]

All paths through the curriculum (midpoint *highlighted*):

*Intro to C.S.* -> Graphics
Intro to C.S. -> *Data Structures* -> Algorithms -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> Compiler
Creative Writing -> *Databases* -> System Administration
*Creative Writing* -> System Administration
Creative Writing -> *Data Structures* -> Algorithms -> COBOL
Creative Writing -> *Data Structures* -> Logic -> COBOL
Creative Writing -> *Data Structures* -> Logic -> Compilers

Visual representation:

                    ____________
                    |          |
                    | Graphics |
               ---->|__________|
               |                          ______________
____________   |                          |            |
|          |   |    ______________     -->| Algorithms |--\     _____________
| Intro to |   |    |            |    /   |____________|   \    |           |
| C.S.     |---+    | Data       |   /                      >-->| COBOL     |
|__________|    \   | Structures |--+     ______________   /    |___________|
                 >->|____________|   \    |            |  /
____________    /                     \-->| Logic      |-+      _____________
|          |   /    ______________        |____________|  \     |           |
| Creative |  /     |            |                         \--->| Compilers |
| Writing  |-+----->| Databases  |                              |___________|
|__________|  \     |____________|-\     _________________________
               \                    \    |                       |
                \--------------------+-->| System Administration |
                                         |_______________________|

Complexity analysis variables:

n: number of pairs in the input

*/

// func findAllMidway(courses [][2]string) []string {
// 	res := []string{}
// 	// prereq course -> next course
// 	coursePreReq := make(map[string][]string)
// 	for _, coursePair := range courses {
// 		if _, ok := coursePreReq[coursePair[0]]; ok == false {
// 			coursePreReq[coursePair[0]] = []string{coursePair[1]}
// 		} else {
// 			coursePreReq[coursePair[0]] = append(coursePreReq[coursePair[0]], coursePair[1])
// 		}
// 	}
// 	for course, nextCourses := range coursePreReq {
// 		if len(nextCourses) >= 2 {
// 			res = append(res, course)
// 		}
// 	}
// 	// for _, coursePair := range courses {
// 	// 	for _, course := range coursePair {
// 	// 		if _, ok := coursePreReq[course]; ok == false {
// 	// 			// last course
// 	// 			fmt.Println(course)
// 	// 		}
// 	// 	}
// 	// }

// 	// map[Algorithms:[COBOL] Creative Writing:[Data Structures System Administration Databases] Data Structures:[Algorithms Logic] Databases:[System Administration] Intro to Computer Science:[Data Structures Graphics] Logic:[COBOL Compilers]]
// 	// fmt.Println(coursePreReq)
// 	return res
// }

// You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program.

// Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program.

// Write a function that takes a list of (prerequisite, course) pairs, and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses, you should return the first one.)

func findMidwayEasy(prerequisites [][2]string) string {
	m1 := make(map[string]int)
	m2 := make(map[string]string) //graph
	var beginning string
	for _, preprerequisite := range prerequisites {
		pre := preprerequisite[0]
		next := preprerequisite[1]
		m2[pre] = next
		m1[next] = 1
		if _, ok := m1[pre]; ok == false {
			beginning = pre
		}
	}
	// fmt.Println(beginning)
	cnt := (len(m1) + 1) / 2

	for i := 1; i <= cnt; i++ {
		beginning = m2[beginning]
	}

	return beginning
}

func findAllMidway(prerequisites [][2]string) {
	set := make(map[string]bool)
	inDegrees := make(map[string]int)
	graph := make(map[string][]string) //graph

	for _, prerequisite := range prerequisites {
		pre := prerequisite[0]
		next := prerequisite[1]
		set[pre] = true
		set[next] = true
		// graph[pre] = next
		if _, ok := graph[pre]; ok == false {
			graph[pre] = []string{next}
		} else {
			graph[pre] = append(graph[pre], next)
		}

		if _, ok := inDegrees[next]; ok == false {
			inDegrees[next] = 1
		} else {
			inDegrees[next] += 1
		}
	}
	paths := []string{}
	beginnings := []string{}
	// ends := []string{}
	for course, _ := range set {
		if _, ok := inDegrees[course]; ok == false {
			beginnings = append(beginnings, course)
		}
	}

	for _, course := range beginnings {
		path := course
		topoDFS(path, course, graph, &paths)
	}

	for _, path := range paths {
		courses := strings.Split(path, "->")
		cnt := len(courses)
		if cnt%2 == 0 {
			fmt.Println(path)
			fmt.Println(courses[cnt/2-1])
		} else {
			fmt.Println(path)
			fmt.Println(courses[cnt/2])
		}
	}
}

func topoDFS(path string, course string, graph map[string][]string, res *[]string) {
	if _, ok := graph[course]; ok == false {
		// tail
		// fmt.Println(path)
		*res = append((*res), path)
	} else {
		nextCourses := graph[course]
		for _, next := range nextCourses {
			newPath := path + "->" + next
			topoDFS(newPath, next, graph, res)
		}
	}
}

func main() {
	input2 := [][2]string{
		[2]string{"Logic", "COBOL"},
		[2]string{"Data Structures", "Algorithms"},
		[2]string{"Creative Writing", "Data Structures"},
		[2]string{"Algorithms", "COBOL"},
		[2]string{"Intro to Computer Science", "Data Structures"},
		[2]string{"Logic", "Compilers"},
		[2]string{"Data Structures", "Logic"},
		[2]string{"Creative Writing", "System Administration"},
		[2]string{"Databases", "System Administration"},
		[2]string{"Creative Writing", "Databases"},
		[2]string{"Intro to Computer Science", "Graphics"},
	}
	input1 := [][2]string{
		{"Foundations of Computer Science", "Operating Systems"},
		{"Data Structures", "Algorithms"},
		{"Computer Networks", "Computer Architecture"},
		{"Algorithms", "Foundations of Computer Science"},
		{"Computer Architecture", "Data Structures"},
		{"Software Design", "Computer Networks"},
	}

	input1_1 := [][2]string{
		{"Data Structures", "Algorithms"},
		// {"Algorithms", "Foundations of Computer Science"},
		// {"Foundations of Computer Science", "Logic"},
	}
	fmt.Println(findMidwayEasy(input1))
	fmt.Println(findMidwayEasy(input1_1))

	findAllMidway(input2)

}
